package com.mlamp.链表;

import com.mlamp.排序算法.基础排序;
import com.mlamp.排序算法.快速排序;

import java.util.Arrays;

public class 删除链表倒数第n个结点 {
    public static void main(String[] args) {
        int[] ints = 基础排序.generateArray(30);
        int[] ints1 = 快速排序.quickSort(ints, 0, ints.length - 1);
        System.out.println(Arrays.toString(ints1));
        LNode lNode = 基础链表.array2LNodeList(ints1);
        LNode lNode1 = deleteNodeReverseN(lNode, 2);
        System.out.println(lNode1.value);
    }


    /**
     * 快慢指针删除链表倒数第n个节点
     *
     * @param head
     * @param n
     * @return
     */

    public static void deletenNode(LNode head, int n) {
        LNode fast, slow;
        fast = slow = head;
        while (n-- > 0 && fast.next != null) {
            fast = fast.next;
        }
        if (fast == null) return;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return;
    }

    private static LNode deleteNodeReverseN2(LNode head, int n) {
        LNode fast, slow;
        fast = slow = head;
        while (n-- > 0 && fast.next != null) {
            fast = fast.next;
        }
        if (fast == null) return head;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }


    public static LNode removeN(LNode head, int n) {
        LNode fast, slow = null;
        fast = slow = head;
        while (--n > 0 && fast.next != null) {
            fast = fast.next;
        }
        if (fast == null) return head;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }


    private static LNode removeNodeFromEndN(LNode head, int n) {
        LNode fast, slow;
        fast = slow = head;
        while (n-- > 0 && fast.next != null) {
            fast = fast.next;
        }
        if (fast == null) return head;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }


    private static LNode deleteNodeReverseN(LNode lNode, int i) {
        LNode fast, slow;
        fast = slow = lNode;

        //there is some bugs
        while (i-- > 0) {
            fast = fast.next;
        }
        if (fast == null) return lNode.next;
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return lNode;
    }
}
